The present invention relates generally to network systems having redundant default gateways and/or routers for receiving traffic from multiple hosts on a LAN. More particularly, the present invention relates to methods and apparatuses for deterministic load balancing across redundant gateway services for a common IP subnet.
Local area networks (LANs) are commonly connected with one another through one or more routers so that a host (a PC or other arbitrary LAN entity) on one LAN can communicate with other hosts on different LANs. Typically, the host is able to communicate directly only with the entities on its local LAN segment. When it receives a request to send a data packet to an address that it does not recognize as being local, it communicates through a router (or other layer-3 device) which determines how to direct the packet between the host and the destination address. Unfortunately, a router may, for a variety of reasons, become inoperative (e.g., a power failure, rebooting, scheduled maintenance, etc.). Such potential router failure has led to the development and use of redundant systems, systems having more than one router to provide a back up in the event of primary router failure. When a router fails, the host communicating through the inoperative router may still remain connected to other LANs if it can send packets to another router connected to its LAN.
Various protocols have been devised to allow a host to choose a router from among a group of routers in a network. Two of these, Routing Information Protocol (or RIP) and ICMP Router Discovery Protocol (IRDP) are examples of protocols that involve dynamic participation by the host. However, because both RIP and IRDP require that the host be dynamically involved in the router selection, performance may be reduced and special host modifications and management may be required.
In a widely used and somewhat simpler approach, the host recognizes only a single “default” router. In this approach, the host is configured to send data packets to the default router when it needs to send packets to addresses outside its own LAN. It does not keep track of available routers or make decisions to switch to different routers. This requires very little effort on the host's part, but has a serious danger. If the default router fails, the host can not send packets outside of its LAN. This will be true even though there may be a redundant router able to take over because the host does not know about the backup. Unfortunately, such systems have been used in mission critical applications such as stock trading. The shortcomings of these early systems led to the development and implementation of a hot standby router protocol (HSRP) by Cisco Systems, Inc. of San Jose, Calif. A more detailed discussion of the earlier systems and of an HSRP type of system can be found in U.S. Pat. No. 5,473,599 (referred to herein as “the '599 patent”), entitled STANDBY ROUTER PROTOCOL, issued Dec. 5, 1995 to Cisco Systems, Inc., which is incorporated herein by reference in its entirety for all purposes. Also, HSRP is described in detail in RFC 2281, entitled “Cisco Hot Standby Router Protocol (HSRP)”, by T. Li, B. Cole, P. Morton and D. Li, which is incorporated herein by reference in its entirety for all purposes.
HSRP forwards data packets from a host on a LAN through a virtual router. The host is configured so that the packets it sends to destinations outside of its LAN are always addressed to the virtual router. The virtual router may be any physical router elected from among a group of routers connected to the LAN. The router from the group that is currently emulating the virtual router is referred to as the “active” router. Thus, packets addressed to the virtual router are handled by the active router. A “standby” router, also from the group of routers, backs up the active router so that if the active router becomes inoperative, the standby router automatically begins emulating the virtual router. This allows the host to always direct data packets to an operational router without monitoring the routers of the network.
A Cisco HSRP system is shown in FIGS. 1-3. As seen in FIG. 1, four gateways 110a-d (for example, routers) operate in a normal mode, providing redundant default gateway services in an active/standby configuration for a common IP subnet. In FIG. 1, the multiple routers 110 (layer-3 switches) form a redundancy group 108 (RG) and share a virtual MAC address 118 and a virtual IP address 116. Hosts 120a-c on a common subnet 130 set their default gateway IP address 126 and MAC address 128 to the virtual addresses 116, 118 within RG 108 for their subnet. In RG 108, a “primary” RG member 110a is elected based on pre-configured priorities. The primary member 110a of the RG 108 responds to all address resolution protocol (“ARP”) requests for the virtual IP address 116, thereby providing default gateway services for all hosts 120 of the common subnet 130 during normal operation. During normal operation, one or more secondary RG members 110b-c of the RG 108 remain in a standby mode. If the primary member 110a of the RG 108 should fail, as shown in FIG. 2, a secondary member 110b will assume the virtual MAC and IP addresses 118, 116, effectively becoming the primary member and thereby providing uninterrupted gateway services to the hosts 120 of common subnet 130 without the need for additional ARP discovery/resolution. While this configuration provides a reliable fail-over function for the gateway devices, the standby members of the RG, while in standby mode in the default configuration, provide no function and carry no traffic initiated by the hosts. Current systems provide no ability to pass traffic initiated within a single common subnet through multiple members of an RG sharing a single virtual gateway IP address in a load balancing arrangement.
Multiple redundancy group versions of the system of FIGS. 1 and 2 are available options, whereby multiple RGs can be configured for a common subnet, each RG possessing its own virtual gateway IP address. As seen in FIG. 3, hosts 120 are configured statically, or via a system such as Cisco's implementation of the Dynamic Host Configuration Protocol (DHCP), as multiple user groups 130a, 130b to use the multiple default gateway IP addresses 116a, 116b, respectively, assigned to RGs 108a, 108b. In RG 108a, member 110a has assumed the primary RG member role, while member 110b is initially a standby member. Members 110c and 110d occupy analogous positions, respectively, within RG 108b. Each grouping of users and RGs then functions as an “independent” system.
This multiple RG configuration provides a load balancing function, but it is through the use of multiple default gateway IP addresses in a common subnet. This requires dividing users/hosts into multiple user groups and configuring the routers as multiple RGs. The administrative task of dividing hosts among multiple default gateways can be tedious and requires customization of the system which many users would prefer to avoid.
Cisco Systems offers multiple methods for load balancing across redundant uplinks from an access layer switch in an enterprise campus or a service provider data center. One method, shown in FIG. 4a, involves using layer-2 mechanisms, which include an additional spanning tree feature from Cisco called Per-VLAN-Spanning-Tree (PVST). With PVST, two or more VLANs (virtual LANs; a VLAN is a LAN based on logical connections instead of physical connections, thereby providing added flexibility) are created on the access layer switch. Using PVST spanning tree tuning, load balancing is achieved by “tuning” half of the VLANs (for example, VLAN-A 405a of FIG. 4a) so that the forwarding path is through one uplink 410 while the remainder of the VLANs (in FIG. 4a, VLAN-B 405b) are “tuned” to use the remaining uplink 420. These multiple VLANs also require multiple IP subnets and a user community that is divided among the multiple VLANs, as seen in FIG. 4a. Using another feature from Cisco called UplinkFast, quick fail-over can be achieved should an individual uplink fail. This load balancing implementation requires a spanning-tree protocol (“STP”) to be present in a triangular switch arrangement, as seen in FIG. 4a, whereby each access switch is homed to each distribution switch and the distribution switches are connected together trunking all VLANs 430, as seen in FIG. 4a. Many users, however, are relinquishing the need for STP in such triangular formations, meaning that PVST-based load balancing will no longer be an option.
As shown in FIG. 4b, in scenarios where STP does not exist in a triangular formation, Cisco's systems can load-share based on alternating the Cisco HSRP-primary function on the redundant layer-3 distribution switches for two or more VLANs-subnets (407a and 407b of FIG. 4b). However, multiple VLANs-subnets are again required on the access layer switch.
In both cases shown in FIGS. 4a and 4b, load balancing is achieved on a per VLAN-subnet basis and requires the user to create a minimum of two VLANs-subnets in each access layer switch. Many users would prefer not having to create a minimum of two VLANs-subnets per access layer switch to achieve load balancing, and yet want to make use of the redundant uplink potential bandwidth. In many cases, it is sufficient to create only one VLAN in each access layer switch. However, as seen from the foregoing examples, a one VLAN system can defeat current load balancing schemes.
Other Cisco features such as protocol filtering, CGMP/IGMP-snooping, and broadcast filtering allow a user to scale a single VLAN to increasingly larger size, often alleviating the need for multiple access VLANs form broadcast domain segmentation. As a result, there is a tendency to have fewer VLANs (and, often, preferably one VLAN) while the need for load balancing among redundant gateways persists. Current methods requiring multiple VLANs at the access layer to achieve load balancing may not suffice or work within various users' systems.
In view of the foregoing, it would be desirable to provide redundant gateway services similar to Cisco's HSRP while providing load balancing of host traffic from a common VLAN-subnet among multiple gateway devices. Such services would leverage resiliency mechanisms of systems like HSRP while adding load balancing capabilities.